package com.ly.algorithm.leetcode.backtracking;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @Classname problem46
 * @Description
 *
 * 给定一个 没有重复 数字的序列，返回其所有可能的全排列。
 *
 * 示例:
 *
 * 输入: [1,2,3]
 * 输出:
 * [
 *   [1,2,3],
 *   [1,3,2],
 *   [2,1,3],
 *   [2,3,1],
 *   [3,1,2],
 *   [3,2,1]
 * ]
 *
 *
 * @Date 2020/12/25 14:56
 * @Author 冷心影翼
 */
public class problem46 {

	public static void main(String[] args) {
		Solution46 solution46 = new Solution46();
		System.out.println(solution46.permute(new int[]{1, 2, 3}));
	}
}

class Solution46 {

	private List<List<Integer>> res = new ArrayList<>();

	public List<List<Integer>> permute(int[] nums) {
		backTracking(nums,new LinkedList<>());
		return res;
	}

	public void backTracking(int[] nums,LinkedList<Integer> cur) {
		if(cur.size() == nums.length)  {
			res.add(new ArrayList<>(cur));
			return;
		}
		for (int i = 0; i < nums.length; i++) {
			if(cur.contains(nums[i]))
				continue;
			cur.add(nums[i]);
			backTracking(nums,cur);
			cur.removeLast();
		}

	}
}
